# nums=[2,3,1,1,4]
nums=[1,1,1,1]

#BFS算法，超时了，这部分
def jump1(nums):
    numsLength=len(nums)
    if numsLength<=1:
        return 0
    #使用广度优先遍历求解
    queueList=[]
    queueList.append(0)
    level=0
    while queueList:
        queueListLen=len(queueList)
        level+=1
        for i in range(queueListLen):
            elemIndex=queueList[0]
            queueList.pop(0)
            if nums[elemIndex]+elemIndex>=numsLength-1:
                #表示下一轮就可以到达最终位置
                return level
            #不然就继续循环
            for j in range(elemIndex+1,nums[elemIndex]+elemIndex+1):
                if j not in queueList and j<numsLength:
                    queueList.append(j)

# print(jump(nums))
def jump(nums):
    numsLen=len(nums)
    ans=0
    st=[False for _ in range(numsLen)]
    queueList=[]
    st[0]=True
    queueList.append(0)
    while queueList:
        size=len(queueList)
        while size>0:
            index=queueList.pop(0)
            if index==numsLen-1:
                return ans
            for i in range(index+1,index+nums[index]+1):
                if i<numsLen and not st[i]:
                    st[i]=True
                    queueList.append(i)
            size-=1
        ans+=1

print(jump(nums))